package com.test.daily.leetcode.y2022.m07.day0724.v02;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author Tom on 2022/7/24
 */
public class Solution {
    public static class Node<V> {
        V value;

        public Node(V value) {
            this.value = value;
        }
    }

    public static class UnionFind<V> {
        HashMap<V, Node> nodes;
        HashMap<Node, Node> fatherMap;
        HashMap<Node, Integer> sizeMap;

        public UnionFind(V[] arr) {
            nodes = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                Node node = new Node(arr[i]);
                nodes.put(arr[i], node);
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public Node findFather(V value) {
            Node node = nodes.get(value);
            Stack<Node> path = new Stack<>();
            while (node != fatherMap.get(node)) {
                path.push(node);
                node = fatherMap.get(node);
            }
            while (path.size() != 0) {
                fatherMap.put(path.pop(), node);
            }
            return node;
        }

        public boolean isSame(V A, V B) {
            return findFather(A) == findFather(B);
        }

        public void union(V A, V B) {
            Node aNode = findFather(A);
            Node bNode = findFather(B);
            if (aNode != bNode) {
                int aSize = sizeMap.get(aNode);
                int bSize = sizeMap.get(bNode);
                Node big = aSize > bSize ? aNode : bNode;
                Node small = aNode == big ? bNode : aNode;
                fatherMap.put(small, big);
                sizeMap.put(big, aSize + bSize);
                sizeMap.remove(small);
            }
        }

        public int setSize() {
            return sizeMap.size();
        }
    }

    public int friendCircleNums(int[][] M) {
        int N = M.length;
        UnionFind2 uf = new UnionFind2(N);
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (M[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.set;
    }

    public static class UnionFind2 {
        public int[] parent;
        public int[] size;
        public int[] help;
        public int set;

        public UnionFind2(int n) {
            parent = new int[n];
            size = new int[n];
            help = new int[n];
            set = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int findFather(int i) {
            int hi = 0;
            while (parent[i] != i) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }

        public boolean isSame(int i, int j) {
            return findFather(i) == findFather(j);
        }

        public int size() {
            return set;
        }

        public void union(int i, int j) {
            int iFather = findFather(i);
            int jFather = findFather(j);
            if (iFather != jFather) {
                int iSize = size[i];
                int jSize = size[j];
                if (iSize > jSize) {
                    parent[jFather] = iFather;
                    size[iFather] = iSize + jSize;
                } else {
                    parent[iFather] = jFather;
                    size[jFather] = iSize + jSize;
                }
                set--;
            }
        }
    }
}
